#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

/*
 0  1  2  3  4
[2, 3, 1, 1, 4] - nums

从位置 0 开始，他最远可以走到 0 + nums[0]，这就表示这个人在一开始的时候，他可以选择走
0, 1, 2, 3, 4, ..., 0 + nums[0] 步

假设这个人选择走 1 步举例，接下来，他最远可以走到 1 + nums[1]，这就表示这个人此时可以选择走：
0, 1, 2, 3, 4, ..., 1 + nums[1] 步
*/
// 从位置 pos 开始，能不能走到末尾
bool helper(int pos, vector<int> nums) {
  if (pos == nums.size() - 1) {
    return true;
  }

  // pos + nums[pos]
  int furthest = min(pos + nums[pos], int(nums.size() - 1)); // 最远走 furthest 步
  int next = pos + 1; // 最少走 1 步

  while (next <= furthest) {
    if (helper(next, nums)) {
      return true;
    }

    next += 1;
  }

  return false;
}

bool canJump(vector<int> nums) {
  return helper(0, nums);
}

int main(int argc, char const *argv[])
{
  /* code */
  // 3, 2, 1, 0, 4
  return 0;
}
